Identification protocols, in particular identification protocols in which a prover proves its identify to a verifier, are well known in the art. Identification protocols and related methods relevant to the present invention are described in the following references:    1. Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, Inc., 1996.    2. Douglas R Stinson, Cryptography Theory and Practice, CRC Press, 1995.    3. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
One particular example of such an identification protocol is the Fiat-Shamir identification protocol, described in U.S. Pat. No. 4,748,668 to Shamir et al, and the related Feige-Fiat-Shamir protocol, described in Applied Cryptography, referred to above, at pages 503-508. Many other such identification protocols are known, with typical examples being described in Applied Cryptography, referred to above, at pages 503-512.
Many identification protocols are based on public key/private key systems, in which a user's public key is published and is known to everyone, while the private key is known only to the user. As is well known in the art, for such a system to work properly it must be extremely difficult to derive the private key from the public key. Typically, prior art protocols of the type discussed herein have the property that knowledge of the private key is preserved, so that the private key itself is revealed neither to an eavesdropper nor to a verifier.
FIG. 1 illustrates a typical prior art identification system. In such a system a prover 100 proves to a verifier 110 the identity of the prover 100, typically by proving knowledge of a private key known to the prover 100. Typically, as is well-known in the art, the method of proof includes generation of one or more random numbers by a random number generator or pseudo random number generator 120, as is well known in the art, comprised in the prover 100. Random numbers so produced are used as part of a protocol 130 for communication between the prover 100 and the verifier 110. Typically, it is important for the security of the protocol that the random number generator produce unpredictable random numbers or pseudo random numbers that can not be predicted or controlled by the verifier 110.
Typical prior art identification protocols usable with the prior art system of FIG. 1 are illustrated in FIGS. 1B and 1C. In FIG. 1B, a true random number generator RNG is used, while in FIG. 1C pseudo-random numbers are generated using values stored in non-volatile storage NVS and acted upon by a cryptographically secure function, also termed herein a one-way hash function, h.
The term “cryptographically secure function” as used herein, is taken, for the purposes of the present specification and claims, to be equivalent to the following terms, which are well-known in the art and which are defined in Applied Cryptography, referred to above, on the indicated pages:                “collision-free hash function”, p. 30; and        “collision-resistant hash function”, p. 429.The term “one-way hash function”, as used throughout the present specification and claims, is used to refer to a cryptographically secure function, unless otherwise specified.        
In a typical prior art protocol, such as those illustrated in FIGS. 1B and 1C, the prover sends an identification string to the verifier, the identification string typically comprising a public key Kp of the prover, either explicitly, typically in the form of a signed key certificate, or implicitly, such that the public key Kp is mathematically derivable from the identification string.
The prover then chooses a random number R and sends f(R) to the verifier, where f is a function that is difficult to reverse, at least difficult to reverse without knowledge of some secret. For example, in Feige-Fiat-Shamir identification, f is the operation of modulo-squaring, with the modulus comprising a composite number having no small prime factors.
The verifier responds with a challenge Q. The prover responds to the challenge Q with an answer A which satisfies some predicate relationship Pred(A,Q,f(R),Kp). The verifier verifies that the predicate relationship is indeed satisfied, thus producing evidence of the identity of the prover.
Typically, the steps mentioned above comprise a single identification round, and multiple identification rounds are typically performed in order to establish the identity of the prover with a high degree of confidence.
More detailed examples of identification protocols are found in U.S. Pat. No. 4,748,668 to Sharir et al and in Applied Cryptography, pages 503-512, both referred to above.
Methods of tampering with protocols such as those described above are described in the following reference:
Ross Anderson and Marcus Kuhn, “Tamper Resistance—A Cautionary Note”, USENIX Association, The Second USENIX Workshop on Electronic Commerce, Proceedings, Oakland, Calif., Nov. 18-21, 1996, pp. 1-11. In particular, in regard to random number generators, Anderson and Kuhn state that “[l]ow voltage can facilitate other attacks too: at least one card has an on-board analogue random number generator, used to manufacture cryptographic keys and nonces, which will produce an output of almost all 1's when the supply voltage is lowered slightly.”
The disclosures of all references mentioned above and throughout the present specification are hereby incorporated herein by reference.